package lc_2812_找出最安全路径;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

	int[][] direct = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

	public int maximumSafenessFactor(List<List<Integer>> grid) {
		int n = grid.size();
		int[][] dist = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dist[i], -1);
		}
		Queue<int[]> q = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (grid.get(i).get(j) == 1) {
					q.add(new int[] { i, j, 0 });
					dist[i][j] = 0;
				}
			}
		}

		while (!q.isEmpty()) {
			int[] c = q.poll();
			int x = c[0], y = c[1], z = c[2];
			for (int[] d : direct) {
				int nx = d[0] + x, ny = d[1] + y;
				if (nx > -1 && nx < n && ny > -1 && ny < n && dist[nx][ny] == -1) {
					dist[nx][ny] = z + 1;
					q.add(new int[] { nx, ny, z + 1 });
				}
			}
		}
		int[][] visit = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(visit[i], -1);
		}
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> dist[b[0]][b[1]] - dist[a[0]][a[1]]);
		visit[0][0] = dist[0][0];
		pq.add(new int[] { 0, 0 });
		while (!pq.isEmpty()) {
			int[] c = pq.poll();
			int x = c[0], y = c[1];
			if (x == n - 1 && y == n - 1) {
				return visit[x][y];
			}
			for (int[] d : direct) {
				int nx = d[0] + x, ny = d[1] + y;
				if (nx > -1 && nx < n && ny > -1 && ny < n && visit[nx][ny] == -1) {
					visit[nx][ny] = Math.min(dist[nx][ny], visit[x][y]);
					pq.add(new int[] { nx, ny });
				}
			}
		}
		return 0;
	}
}